// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------
Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

// Dummy functions -- so we can compile our later assignments 
// Note -- without a correct implementation of Condition::Wait(), 
// the test case in the network assignment won't work!

//---------------------------
//-  Modified as Homework1  -
//-  by  OceanMaster        -
//---------------------------
Lock::Lock(char* debugName) 
{
	name = debugName;			//store name for debug
	waitQueue = new List;		//the queue to store waiting thread
	owner = NULL;
	free = true;
}

Lock::~Lock() 
{
	delete waitQueue;			//release queue memory
}

void Lock::Acquire()
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff);	//make it atomic
	DEBUG('1',"Thread '%s' is trying to acquire Lock '%s'\n",currentThread->getName(),name);
	if(isHeldByCurrentThread())	//if current thread is already holding the Lock
	{
		DEBUG('1',"Thread '%s' is already holding the Lock '%s', can't acquire it again\n",currentThread->getName(),name);
		//debug message, '1' is the debug flag for assignment1
		interrupt->SetLevel(oldLevel);
		return;
	}	
	if(free)					//if the Lock is free
	{
		DEBUG('1',"Thread '%s' acquired Lock '%s'\n",currentThread->getName(),name);
		free = false;			//take the Lock
		owner = currentThread;	//register self
	}
	else						//otherwise, the Lock is already taken by others
	{
		DEBUG('1',"Thread '%s' will wait because Lock '%s' is already held by '%s'\n",currentThread->getName(),name,owner->getName());
		waitQueue->Append((void *)currentThread);	//add self to wait queue
		currentThread->Sleep();						//go to sleep
	}
	interrupt->SetLevel(oldLevel);					//leaving critical section
}

//Assupmtion: Lock is busy.
void Lock::Release()
{
	Thread * thread;
	
	IntStatus oldLevel = interrupt->SetLevel(IntOff);	//make it automic
	DEBUG('1',"Thread '%s' is trying to release Lock '%s'\n",currentThread->getName(),name);

	if(!isHeldByCurrentThread())	//only owner of the Lock can release it
	{
		DEBUG('1',"Thread '%s' is not owner of Lock '%s', can't release it\n",currentThread->getName(),name);
		interrupt->SetLevel(oldLevel);
		return;
	}


	thread = (Thread *) waitQueue->Remove();
	if( thread!=NULL )			//if waitQueue is not empty, take one thread off it
	{
		DEBUG('1',"Thread '%s' hands over Lock '%s' to Thread '%s'\n",currentThread->getName(),name, thread->getName());
		owner = thread;			//hand over ownership
		scheduler->ReadyToRun(thread); //put it in ready queue, state ready : Wake it up
	}
	else						//otherwise, reset the Lock
	{
		DEBUG('1',"Thread '%s' resets Lock '%s' because no one is waiting\n",currentThread->getName(),name);
		free = true;
		owner = NULL;
	}

	interrupt->SetLevel(oldLevel);
}

bool Lock::isHeldByCurrentThread()// is current thread holding the lock?
{
	return (currentThread==owner);
}

//=================================
//	Added as Project2
//  by OceanMaster
//=================================
int Lock::getWaitLength()
{
	return waitQueue->Count();
}
//=================================


/**********************************
 *Added as Assignment1:OceanMaster*
 *								  *
 *Without professor's instruction *
 *        COULD BE WRONG		  *
 *      WATCH OUT FOR BUGS		  *
 **********************************/

Condition::Condition(char* debugName) 
{
	name = debugName;
	lock = NULL;
	waitQueue = new List;
}

Condition::~Condition()
{
	delete waitQueue;
}

//Confusion:
//    is it One condition can only be related to One Lock?
//    why have to trans a Lock as varible every time call a method?it can be buggy

//OperationDescription: 1) wait on the event 
//						2) if lock register is empty, register the Lock
//Assumption: 1) current thread has alread owned the Lock
//            2) the lock passed in is the lock UNLESS no lock occupied yet
//			  3) Lock passed in is not NULL
void Condition::Wait(Lock* conditionLock) 
{
	//is an interrupt disable needed?
	//otherwise may affect print msg
	IntStatus oldLevel = interrupt->SetLevel(IntOff);//set interrupt off, so that operation between release lock and sleep is atomic
		
	DEBUG('1',"Thread '%s' is trying to wait on condition '%s'\n",currentThread->getName(),name);

	if(conditionLock == NULL)		//Lock shouldn't be null
	{
		DEBUG('1',"Thread '%s' 's Lock is NULL, fail waiting\n", currentThread->getName());
		interrupt->SetLevel(oldLevel);
		return;
	}
	
	if(!conditionLock->isHeldByCurrentThread())	//if thread doens't own the Lock, can't go on

	{
		DEBUG('1',"Thread '%s' is not holding Lock '%s', can't go on\n", currentThread->getName(), conditionLock->getName());
		interrupt->SetLevel(oldLevel);
		return;
	}
	
	if(lock == NULL)				//register Lock
	{
		lock = conditionLock;
		DEBUG('1',"Thread '%s' registered Lock '%s' on condition '%s'\n",currentThread->getName(),conditionLock->getName(),name);
	}

	if(conditionLock != lock)		//If not the lock registered, fail it
	{
		DEBUG('1',"Thread '%s' 's Lock is not the Lock related, fail waiting\n", currentThread->getName());
		interrupt->SetLevel(oldLevel);
		return;
	}
		
	DEBUG('1',"Thread '%s' is going to wait on condition '%s'\n",currentThread->getName(),name);
	
	//ASSERT(FALSE);
	
	waitQueue->Append((void *)currentThread);//put self in wait queue
	conditionLock->Release();		//release the Lock before sleep, so that others can enter;
	currentThread->Sleep();			//sleep
	conditionLock->Acquire();		//re-acquire the lock; Mesa-style	
	
	interrupt->SetLevel(oldLevel);
}

//OperationDescription: 1) wake one waiting thread up
//						2) after that, if no one is waiting, reset lock register
//Assumption: 1) current thread holding the Lock
//			  2) the Lock is registered
//			  3) passed in Lock is not NULL
void Condition::Signal(Lock* conditionLock)
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff);	//make operation atomic, avoid disturbing
	
	DEBUG('1',"Thread '%s' is trying to signal condition '%s'\n",currentThread->getName(),name);

	if(conditionLock == NULL)							//Lock shouldn't be null
	{
		DEBUG('1',"Thread '%s' 's Lock is NULL, fail signaling\n", currentThread->getName());
		interrupt->SetLevel(oldLevel);
		return;
	}
	
	if(!conditionLock->isHeldByCurrentThread())			//if thread doens't own the Lock, can't go on
	{
		DEBUG('1',"Thread '%s' is not holding Lock '%s', can't go on\n", currentThread->getName(), conditionLock->getName());
		interrupt->SetLevel(oldLevel);
		return;
	}
	
	if(lock!=conditionLock)								//if Lock is not the one registered, fail
	{
		DEBUG('1',"Thread '%s' 's Lock is not the one registered on condition '%s', can't go on\n", currentThread->getName(), name);
		interrupt->SetLevel(oldLevel);
		return;
	}

	DEBUG('1',"Thread '%s' is going to signal condition '%s'\n",currentThread->getName(),name);
	
	Thread * thread = (Thread *)waitQueue->Remove();
	if(thread!=NULL)									//if waiting queue is not empty, wake one waiting thread up
		scheduler->ReadyToRun(thread);

	if(waitQueue->IsEmpty())							//If waiting queue is empty now, reset Lock register
		lock=NULL;
	
	interrupt->SetLevel(oldLevel);
}

//OperationDescription: 1) wake all waiting thread up
//						2) reset Lock register
//Assumption: 1) current thread holding the Lock
//			  2) passed in Lock is not null
//			  3) passed in Lock is registered
void Condition::Broadcast(Lock* conditionLock)
{
	IntStatus oldLevel = interrupt->SetLevel(IntOff);	//make operation atomic, avoid disturbing
	
	DEBUG('1',"Thread '%s' is trying to broadcasting condition '%s'\n",currentThread->getName(),name);

	if(conditionLock == NULL)							//Lock shouldn't be null
	{
		DEBUG('1',"Thread '%s' 's Lock is NULL, fail broadcasting\n", currentThread->getName());
		interrupt->SetLevel(oldLevel);
		return;
	}
	
	if(!conditionLock->isHeldByCurrentThread())			//if thread doens't own the Lock, can't go on
	{
		DEBUG('1',"Thread '%s' is not holding Lock '%s', can't go on\n", currentThread->getName(), conditionLock->getName());
		interrupt->SetLevel(oldLevel);
		return;
	}
	
	if(lock!=conditionLock)								//if Lock is not the one registered, fail
	{
		DEBUG('1',"Thread '%s' 's Lock is not the one registered on condition '%s', can't go on\n", currentThread->getName(), name);
		interrupt->SetLevel(oldLevel);
		return;
	}

	DEBUG('1',"Thread '%s' is going to broadcast condition '%s'\n",currentThread->getName(),name);
	
	Thread * thread = (Thread *)waitQueue->Remove();
	while(thread!=NULL)									//if waiting queue is not empty, wake all  waiting thread up
	{
		scheduler->ReadyToRun(thread);
		thread = (Thread *)waitQueue->Remove();
	}

	lock = NULL;										//reset lock register, because waiting list must be empty now

	interrupt->SetLevel(oldLevel);
}

//=================================
//	Added as Project2
//  by OceanMaster
//=================================
int Condition::getWaitLength()
{
	return waitQueue->Count();
}
//=================================



/****************************
 *    END : OceanMaster     *
 ****************************/

